//1.分治-快排-数组中的第k个最大元素
class Solution {
public:
    int get_key(vector<int> nums, int l, int r)
    {
        return nums[l + rand() % (r - l + 1)];
    }

    int quick_sort(vector<int> nums, int l, int r, int k)
    {
        if(l == r) return nums[l];

        //数组分三块
        //[l, left] [left + 1, i - 1] [i, right - 1] [right, r]
        int p = get_key(nums, l, r);
        int left = l - 1, right = r + 1, i = l;
        while(i < right)
        {
            if(nums[i] == p) i++;
            else if(nums[i] > p) swap(nums[++left], nums[i++]);
            else swap(nums[--right], nums[i]);
        }

        int a = left - l + 1, b = right - 1 - left, c = r - right + 1;
        if(a >= k) return quick_sort(nums, l, left, k);
        else if(k <= a + b) return p;
        else return quick_sort(nums, right, r, k - a - b);
    }

    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        srand((unsigned int)time(nullptr));
        return quick_sort(nums, 0, n - 1, k);
    }
};


//2.分治-快排-最小的k个数
class Solution {
public:
    int get_key(vector<int> nums, int l, int r)
    {
        return nums[l + rand() % (r - l + 1)];
    }

    void qsort(vector<int>& nums, int l, int r, int cnt)
    {
        if(l >= r) return;
        int p = get_key(nums, l, r);
        int left = l - 1, right = r + 1, i = l;
        while(i < right)
        {
            if(nums[i] == p) i++;
            else if(nums[i] < p) swap(nums[++left], nums[i++]);
            else swap(nums[--right], nums[i]);
        }
        int a = left - l + 1, b = right - left - 1;
        if(cnt < a) qsort(nums, l, left, cnt);
        else if(cnt <= a + b) return;
        else qsort(nums, right, r, cnt - a - b);
    }

    vector<int> inventoryManagement(vector<int>& nums, int cnt) {
        srand((unsigned int)time(nullptr));
        qsort(nums, 0, nums.size() - 1, cnt);
        return {nums.begin(), nums.begin() + cnt};
    }
};